package mess;

import javax.swing.*;
import java.time.temporal.Temporal;
import java.util.*;

public class LeeCode_1255 {
    public static void main(String[] args) {
        String[] words = new String[]{"dog","cat","dad","good"};
        char[] letters = new char[]{'a','a','c','d','d','d','g','o','o'};
        int[] score = new int[]{1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0};
        String[] words1 = new String[]{"xxxz","ax","bx","cx"};
        char[] letters1 = new char[]{'z','a','b','c','x','x','x'};
        int[] score1 = new int[]{4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10};
        String[] words2 = new String[]{"leetcode"};
        char[] letters2 = new char[]{'l','e','e','c','o','d','e'};
        int[] score2 = new int[]{0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0};
        //System.out.println(maxScoreWords(words, letters, score));
        //System.out.println(maxScoreWords(words2, letters2, score2));

       /* ["add","dda","bb","ba","add"]
["a","a","a","a","b","b","b","b","c","c","c","c","c","d","d","d"]
[3,9,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]*/
        String[] words3 = new String[]{"add","dda","bb","ba","add"};
        char[] letters3 = new char[]{'a','a','a','a','b','b','b','b','c','c','c','c','c','d','d','d'};
        int[] score3 = new int[]{3,9,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
        System.out.println(maxScoreWords(words3, letters3, score3));

    }

    private static int maxScoreWords(String[] words, char[] letters, int[] score) {
        TreeSet<Integer> res = new TreeSet<>();
        Map<Character, Integer> map = new HashMap<>();
        for (char letter : letters) {
            if (map.containsKey(letter))
                map.put(letter, map.get(letter) + 1);
            else
                map.put(letter, 1);
        }

        backTrick(res, words, map, score, 0, 0);
        return res.last();
    }

    private static void backTrick(TreeSet<Integer> res, String[] words, Map<Character, Integer> map, int[] score, int sum, int index){
        int len = words.length;
        if (index > len - 1)
            return;

        for (int i = index; i < len; i++) {
            boolean flag = true;
            String word = words[i];

            //初始map
            Map<Character, Integer> tempMap = new HashMap<>(map);

            //初始sum
            int tempSum = sum;

            for (int j = 0; j < word.length(); j++) {
                char c = word.charAt(j);
                //字母无剩余或不存在
                if (map.get(c) == null || map.get(c) == 0){
                    //单词表遍历到末尾且末尾单词未成功
                    flag = false;
                    break;
                }
                //字母有剩余, 更新剩余字母数量和sum
                else {
                    sum += score[c - 97];
                    map.put(c, map.get(c) - 1);
                }
            }

            //单词拼成功, 递归
            if (flag) {
                //单词表遍历到末尾且末尾单词成功, 添加sum
                if (i == len - 1) {
                    res.add(sum);
                    return;
                }
                // 递归
                else
                    backTrick(res, words, tempMap, score, tempSum, i + 1);
            }
            //单词拼失败, 添加初始sum, 递归
            else {
                res.add(tempSum);
                if (i < len - 1){
                    backTrick(res, words, tempMap, score, tempSum, i + 1);
                }
                break;
            }
        }
    }
}
